# 作者: 陈其志 
# 2025年02月24日15时33分10秒 
# 2716847110@qq.com
import random


class Sort:
    """
    堆排：层次建树的完全二叉树特性：最后一个父亲节点的下表是n/2 -1
    左孩子的下标是2*dad +1
    重要过程是调整大根堆
    """

    def __init__(self, n, nums_range):
        self.n = n  # 排序数目
        self.arr = []
        self.nums_range = nums_range
        self.random_nums()

    def random_nums(self):
        for i in range(self.n):
            self.arr.append(random.randint(0, self.nums_range - 1))

    def adjust_max_heap(self, parent_index, arr_len):
        """
        把某一棵子树调整为大根堆
        :param parent_index: 要调整的位置
        :param arr_len: 列表的长度
        :return:
        """
        arr = self.arr
        dad = parent_index
        son = 2 * dad + 1
        while son < arr_len:
            # 检查是否有右孩子
            if son + 1 < arr_len and arr[son] < arr[son + 1]:
                son += 1
            if arr[dad] < arr[son]:
                arr[son], arr[dad] = arr[dad], arr[son]
                dad = son
                son = 2 * dad + 1
            else:
                break

    def heap_sort(self):
        arr = self.arr
        # 把列表调整为大根堆
        for parent_index in range(self.n // 2 - 1, -1, -1):  # 牢记range的函数用法
            self.adjust_max_heap(parent_index, self.n)
        # 交换堆顶
        for arr_len in range(self.n - 1, 0, -1):
            arr[arr_len], arr[0] = arr[0], arr[arr_len]
            self.adjust_max_heap(0, arr_len)


if __name__ == '__main__':
    s = Sort(10, 100)
    print(s.arr)
    s.heap_sort()
    print(s.arr)
